package diff;

import java.util.List;
import java.util.ArrayList;

/**
 * Dumb diff calculator. The simplest (and exact) implementation of finding longest common sequence.
 * Time: O(MN)
 * Memory consumption: O(MN)
 *
 * @author Arseny Kapoulkine
 */
public class DumbDiffCalculator implements DiffCalculator
{
    private static final int null_entry = 0;
    private static final int chars_equal = 1;
    private static final int wout_source_element = 2;
    private static final int wout_dest_element = 3;

    private static class TableEntry
    {
        int length; // max length of subsequence
        int choice;
    }

    private TableEntry[][] table;

    public Diff calculate(List source, List dest)
    {
        int N = source.size();
        int M = dest.size();

        // construct table
        //      N+1
        //  M+1  x
        table = new TableEntry[M + 1][N + 1];

        for (int j = 0; j <= M; ++j)
            for (int i = 0; i <= N; ++i)
                table[j][i] = new TableEntry();

        // Fill table
        table[0][0].length = 0;
        table[0][0].choice = null_entry;

        for (int i = 1; i <= N; ++i)
        {
            table[0][i].length = 0;
            table[0][i].choice = wout_source_element;
        }

        for (int j = 1; j <= M; ++j)
        {
            table[j][0].length = 0;
            table[j][0].choice = wout_dest_element;
        }

        for (int j = 1; j <= M; ++j)
            for (int i = 1; i <= N; ++i)
            {
                // Do we have equal elements?
                if (source.get(i-1).equals(dest.get(j-1))) 
                {
                    table[j][i].choice = chars_equal;
                    // the sequence is that for the previous cell + equal symbol
                    table[j][i].length = table[j-1][i-1].length + 1;
                }
                else
                {
                    int wout_source_element_length = table[j][i-1].length;
                    int wout_dest_element_length = table[j-1][i].length;

                    // estimate maximum
                    if (wout_source_element_length < wout_dest_element_length)
                    {
                        table[j][i].length = wout_dest_element_length;
                        table[j][i].choice = wout_dest_element;
                    }
                    else
                    {
                        table[j][i].length = wout_source_element_length;
                        table[j][i].choice = wout_source_element;
                    }
                }
            }

        // Now we have the table - let's build our diff recursively

        Diff result = recursiveBuild(N, M, dest);

        table = null;

        return result;
    }

    private static Diff diffAdd(Diff d, int where, String what)
    {
        DiffPacket lastPacket = d.getPackets().isEmpty() ? null : (DiffPacket)d.getPackets().get(d.getPackets().size()-1);

        if (lastPacket == null || lastPacket.start != where)
        {
            DiffPacket p = new DiffPacket(where, where, new ArrayList());
            p.contents.add(what);

            d.getPackets().add(p);
        }
        else
        {
            // concatenate
            lastPacket.contents.add(what);
        }

        return d;
    }

    private static Diff diffRemove(Diff d, int where)
    {
        DiffPacket lastPacket = d.getPackets().isEmpty() ? null : (DiffPacket)d.getPackets().get(d.getPackets().size()-1);

        if (lastPacket == null || lastPacket.end != where)
        {
            d.getPackets().add(new DiffPacket(where, where + 1));
        }
        else
        {
            // concatenate
            lastPacket.end++;
        }

        return d;
    }

    private Diff recursiveBuild(int i, int j, List dest)
    {
        TableEntry e = table[j][i];

        switch (e.choice)
        {
            case chars_equal:
            {
                // we have equal chars, so just get the previous diff
                return recursiveBuild(i-1, j-1, dest);
            }

            case wout_dest_element:
            {
                // table[j-1][i] prevailed, which means that we have to take previous diff
                // and add j-th dest element
                return diffAdd(recursiveBuild(i, j-1, dest), i, (String)dest.get(j-1));
            }

            case wout_source_element:
            {
                // table[j][i-1] prevailed, which means that we have to take previous diff
                // and remove i-th source element
                return diffRemove(recursiveBuild(i-1, j, dest), i-1);
            }

            default:
            {
                return new Diff();
            }
        }
    }
}
